struct Deque<T> { data: Vec<T> }  
impl<T> Deque<T> {  

    // 前端插入（时间复杂度 O(n)）
    fn push_front(&mut self, item: T) { 
        /* TODO */ 
        self.data.insert(0, item)
    }  

    // 后端弹出（时间复杂度 O(1)）
    fn pop_back(&mut self) -> Option<T> { 
        /* TODO */ 
        self.data.pop()
    }  

    // 扩展功能（可选实现）
    #[allow(dead_code)]
    fn push_back(&mut self, item: T) {
        self.data.push(item)
    }

    #[allow(dead_code)]
    fn pop_front(&mut self) -> Option<T> {
        if self.data.is_empty() {
            None
        } else {
            Some(self.data.remove(0))
        }
    }
}  

#[test] fn test_deque() {
    /* 测试两端操作 */ 
    let mut dq = Deque { data: Vec::new() };
    
    // 测试前端插入 + 后端弹出
    dq.push_front(1);
    dq.push_front(2);
    assert_eq!(dq.pop_back(), Some(1));
    assert_eq!(dq.pop_back(), Some(2));
    assert_eq!(dq.pop_back(), None);

    // 测试混合操作
    dq.push_back(3);
    dq.push_front(4);
    assert_eq!(dq.pop_front(), Some(4));
    assert_eq!(dq.pop_back(), Some(3));
}  

// 添加交互演示
fn main() {
    let mut deque = Deque { data: Vec::new() };
    
    // 演示字符串操作
    deque.push_front("world".to_string());
    deque.push_front("hello".to_string());
    println!("{:?}", deque.pop_back());  // Some("world")
    
    // 演示泛型支持
    let mut int_deque = Deque { data: vec![2, 1] };
    int_deque.push_front(3);
    println!("Final deque: {:?}", int_deque.data);  // [3, 2, 1]
}